import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zx
 * @date date 2019-11-30 21:31:33
 * --------------
 * 中缀转逆波兰（后缀）
 * --------------
 */
public class ReversePolish {
    public static void main(String args[]){
        String str = "3+9*7+(2*1+7)*2";
        System.out.println(reversePolish(str));
        System.out.println(sumReversePolish(reversePolish(str)));
    }

    public static String reversePolish(String str){
        //String[] strArray = str.split("");
        String str1;
        char[] strArray = str.toCharArray();
        String[] operator = {"+","-","/","*","(",")"};
        List<String> list = Arrays.asList(operator);
        LinkedList<String> list1 = new LinkedList<String>();  //输出栈
        LinkedList<String> list2 = new LinkedList<String>();   //操作符栈
        for(int i = 0;i < strArray.length; i++){
			/*该部分为查bug过程 ，一步一步看输出是否一致
			 if(i == 14) {
				Iterator<String> it1 = list1.iterator();
				Iterator<String> it2 = list2.iterator();
				while(it1.hasNext()) {
					System.out.print(it1.next() + " ,");
				}
				System.out.println();
				while(it2.hasNext()) {
					System.out.print(it2.next() + " ,");
				}
				System.out.println();
				//System.exit(-1);
			}*/

            if(Character.isDigit(strArray[i]) || Character.isLetter(strArray[i])){     //如果是操作数或者字母直接输出
                list1.add(Character.toString(strArray[i]));
            }else if(list.contains(Character.toString(strArray[i]))){ //如果是操作符
                if(list2.size() == 0){  //操作符栈空
                    list2.addFirst(Character.toString(strArray[i]));                 //操作符入栈
                }else { //操作符栈非空
                    if(Character.toString(strArray[i]).equals("(")){ //匹配到左括号
                        list2.addFirst(Character.toString(strArray[i]));                 //操作符入栈
                    } else if(Character.toString(strArray[i]).equals(")")){ //匹配到右括号
                        String[] strA = list2.toArray(new String[0]);
                        for(int j = 0;j < strA.length;j++) {
                            do{
                                if(list2.size() == 0) {
                                    //这里写不写都行，因为有括号不可能在第一个位置
                                }else {
                                    if(strA[j].equals("(")){
                                        list2.pollFirst();
                                        j = strA.length - 1;
                                    }else{
                                        list1.add(list2.pollFirst());
                                    }
                                }
                            }while(strA[j].equals("quit"));
                        }
                    }
                    //如果是加号或者减号，则除了遇到左括号，全部要出栈
                    else if(Character.toString(strArray[i]).equals("+") || Character.toString(strArray[i]).equals("-")){
                        String[] strB = list2.toArray(new String[0]); //要对操作符栈进行操作，所以不能使用Iterator进行操作（iterator操作的时候不能进行list的改动）
                        if(strB[0].equals("(")){
                            list2.addFirst(Character.toString(strArray[i]));
                        }else {
                            for(int k = 0;k < strB.length;k++) {
                                if(strB[k].equals("(")) {
                                    list2.addFirst(Character.toString(strArray[i]));
                                    k = strB.length - 1;  //遇到左括号直接入栈，跳出循环，下面类似
                                }else {
                                    do{
                                        if(list2.size() == 0) {
                                            list2.addFirst(Character.toString(strArray[i]));
                                        }else {
                                            list1.add(list2.pollFirst());
                                        }
                                    }while(strB[k].equals("quit"));
                                }
                            }
                        }
                        if(list2.size() == 0){  //因为栈里面的数据都出栈了，所以刚扫描的符号要进栈，前提是没有左括号
                            list2.addFirst(Character.toString(strArray[i]));
                        }
                    }
                    //如果是乘号或者除号，栈顶元素为+或者-或者（进栈，*或者、出栈
                    else if(Character.toString(strArray[i]).equals("*") || Character.toString(strArray[i]).equals("/")){
                        String[] strC = list2.toArray(new String[0]);
                        if(strC[0].equals("(")) {
                            list2.addFirst(Character.toString(strArray[i]));
                        }else {
                            for(int l = 0;l < strC.length;l++) {
                                if(strC[l].equals("(")) {
                                    list2.addFirst(Character.toString(strArray[i]));
                                    l = strC.length - 1;
                                }else {
                                    do{
                                        if(list2.size() == 0){
                                            list2.addFirst(Character.toString(strArray[i]));
                                        }else {
                                            if(strC[l].equals("*") || strC[l].equals("/")){
                                                list1.add(list2.pollFirst());
                                            }else if(strC[l].equals("+") || strC[l].equals("-")){
                                                list2.addFirst(Character.toString(strArray[i]));
                                            }else {}
                                        }
                                    }while(strC[l].equals("quit"));
                                }
                            }
                        }
                        if(list2.size() == 0){
                            list2.addFirst(Character.toString(strArray[i]));
                        }
                    }
                }
            }
            else {
                System.out.println("输入字符串中的第个" + i + "符号 " + strArray[i] + "无法识别,请核对！");
            }
        }
        //字符串扫描完毕，把操作符栈剩下的操作符依次取出到输出栈
        int len = list2.size();
        for(int p = 0;p < len;p++){
            list1.add(list2.pollFirst());
        }
        String[] strOutput = list1.toArray(new String[0]);
        StringBuffer sb = new StringBuffer();
        for(int i = 0; i < strOutput.length; i++){
            sb. append(strOutput[i]);
        }
        str1 = sb.toString();

        return str1;
    }


    //后序表达式求值，要求中序序列只能有数字不能有字母
    public static int sumReversePolish(String str){
        //char[] strArray = str.toCharArray();
        String[] strArray = str.split("");
        LinkedList<Integer> list1 = new LinkedList<Integer>(); //存操作数
        int a = 0,b = 0,sum = 0;
        for (int i = 0; i < strArray.length; i++) {
            if(strArray[i].equals("+") || strArray[i].equals("-") || strArray[i].equals("*") || strArray[i].equals("/")){
                sum = 0;
                a = list1.pollFirst();  //获取第一个数
                b = list1.pollFirst();  //获取第二个数
                switch(strArray[i]) {
                    case "+": sum = b + a; list1.addFirst(sum); break;
                    case "-": sum = b - a; list1.addFirst(sum); break;
                    case "*": sum = b * a; list1.addFirst(sum); break;
                    case "/": sum = b / a; list1.addFirst(sum); break;
                }
            }else {
                list1.addFirst(Integer.valueOf(strArray[i]).intValue()); //数字的话直接加入列表
            }
        }
        return sum;
    }
}
